/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30/FONT#10=MATH50



␈↓ ↓H␈↓α␈↓ ∧gCONDITIONAL EXPRESSIONS

␈↓ ↓H␈↓␈↓ α_The␈α∂object␈α∂of␈α∂this␈α∂note␈α∂is␈α⊂to␈α∂illustrate␈α∂the␈α∂mathematical␈α∂properties␈α∂of␈α∂and␈α⊂claim␈α∂general
␈↓ ↓H␈↓mathematical␈α
usefulness␈α
for␈α
the␈α
conditional␈α
expression␈α
notation␈α
used␈α
in␈α
computer␈α∞science.␈α
 They
␈↓ ↓H␈↓are␈α
especially␈α
convenient␈α
for␈α
defining␈α
and␈αmaking␈α
formal␈α
calculations␈α
with␈α
functions␈α
defined␈αby
␈↓ ↓H␈↓different␈α∩formulas␈α∩on␈α∩different␈α∩parts␈α∩of␈α∩their␈α∩domains.␈α∩ The␈α∩provide␈α∩a␈α∪convenient␈α∩domain-
␈↓ ↓H␈↓independent␈α∂way␈α∂of␈α∂making␈α∂a␈α∂recursive␈α∞definitions,␈α∂and␈α∂they␈α∂have␈α∂a␈α∂simple␈α∂elementary␈α∞theory
␈↓ ↓H␈↓which is a generalization of propositional calculus.

␈↓ ↓H␈↓␈↓ α_Conditional␈α∂expressions␈α∂have␈α∂long␈α∂been␈α∂used␈α⊂in␈α∂mathematics␈α∂as␈α∂the␈α∂right␈α∂hand␈α⊂sides␈α∂of
␈↓ ↓H␈↓definitions like
␈↓ ↓H␈↓↓␈↓ ∧Xx ␈↓if␈↓↓ x ≥ 0,
␈↓ ↓H␈↓↓1)␈↓ α8  |x| =
␈↓ ↓H␈↓↓␈↓ ∧H-x ␈↓otherwise.

␈↓ ↓H␈↓However,␈αthis␈αdoesn't␈αmake␈αconditional␈αexpressions␈αfull␈αmathematical␈αcitizens,␈αbecause␈αthey␈αaren't
␈↓ ↓H␈↓used in mathematical sentences other than definitions or as subexpressions.

␈↓ ↓H␈↓␈↓ α_The␈α⊃most␈α⊃common␈α⊃computer␈α⊃science␈α⊃notation␈α⊃for␈α⊃conditional␈α⊃expressions␈α⊃is␈α⊃that␈α⊃of␈α⊃the
␈↓ ↓H␈↓programming language Algol 60.  In that notation, (1) is written

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓|x| = ␈↓αif␈↓↓ x ≥ 0 ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ -x␈↓.

␈↓ ↓H␈↓It␈αis␈α
customary␈αto␈α
print␈αthe␈αwords␈α
␈↓αif␈↓,␈α␈↓αthen␈↓␈α
and␈α␈↓αelse␈↓␈α
in␈αbold␈αface␈α
type␈αand␈α
to␈αsingly␈αunderline␈α
them
␈↓ ↓H␈↓in handwriting or typescript.  A more compact but less mnemonic notation writes (1) as

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓|x| = (x ≥ 0 → x, -x)␈↓.

␈↓ ↓H␈↓We will use the ␈↓αif␈↓-␈↓αthen␈↓-␈↓αelse␈↓ notation.

␈↓ ↓H␈↓␈↓ α_A simple conditional expression has the general form

␈↓ ↓H␈↓4)␈↓ α8  ␈↓↓␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ b␈↓

␈↓ ↓H␈↓where␈α␈↓↓p␈↓␈αis␈α
an␈αexpression␈αthat␈α
can␈αbe␈αtrue␈α
or␈αfalse␈αand␈α
␈↓↓a␈↓␈αand␈α␈↓↓b␈α
take␈↓␈αon␈αvalues␈α
in␈αsome␈αdomain␈α
␈↓↓D.␈↓
␈↓ ↓H␈↓Thus␈αin␈α(2),␈α␈↓↓a␈↓␈α
and␈α␈↓↓b␈↓␈αare␈αexpressions␈α
whose␈αvalues␈αare␈αreal␈α
numbers.␈α The␈αvalue␈αof␈α
(4)␈αis␈αthat␈αof␈α
␈↓↓a␈↓
␈↓ ↓H␈↓if ␈↓↓p␈↓ is true and that of ␈↓↓b␈↓ if ␈↓↓p␈↓ is false.  An extended form of conditional expression

␈↓ ↓H␈↓5)␈↓ α8  ␈↓↓␈↓αif␈↓↓ p␈↓β1␈↓↓ ␈↓αthen␈↓↓ a␈↓β1␈↓↓ ␈↓αelse␈↓↓ ␈↓αif␈↓↓ p␈↓β2␈↓↓ ␈↓αthen␈↓↓ a␈↓β2␈↓↓  ... ␈↓αelse␈↓↓ ␈↓αif␈↓↓ p␈↓βn␈↓↓ ␈↓αthen␈↓↓ a␈↓βn␈↓↓ ␈↓αelse␈↓↓ a␈↓βn+1␈↓

␈↓ ↓H␈↓is␈αalso␈αused.␈α Its␈αvalue␈αis␈αthat␈αof␈α␈↓↓a␈↓βi␈↓,␈αwhere␈α␈↓↓i␈↓␈αis␈αthe␈αindex␈αof␈αthe␈αfirst␈αof␈α␈↓↓p␈↓β1␈↓↓ ... p␈↓βn␈↓␈αthat␈αis␈αtrue,␈αand
␈↓ ↓H␈↓␈↓↓a␈↓βn+1␈↓ if none of the ␈↓↓p␈↓'s is true.  The equation

␈↓ ↓H␈↓6)␈↓ α8  ␈↓↓triangle(x) = ␈↓αif␈↓↓ x < -1 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x < 0 ␈↓αthen␈↓↓ 1 + x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x < 1 ␈↓αthen␈↓↓ 1 - x ␈↓αelse␈↓↓ 0␈↓

␈↓ ↓H␈↓defines the function graphed in figure 1.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ ε⊃Figure 1

␈↓ ↓H␈↓␈↓ α_Conditional␈α
expressions␈α
provide␈α
an␈α
orderly␈α
if␈α
somewhat␈α
long-winded␈α
way␈α
of␈α
making␈α
certain
␈↓ ↓H␈↓calculations by cases.  Thus

␈↓ ↓H␈↓7)␈↓ α8 ␈↓↓triangle(x) + triangle(1+x) =

␈↓ ↓H␈↓↓                =␈α(␈↓αif␈↓↓␈αx␈α<␈α-1␈α␈↓αthen␈↓↓␈α0␈α␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈αx␈α<␈α0␈α␈↓αthen␈↓↓␈α1+x␈α␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈αx␈α<␈α1␈α␈↓αthen␈↓↓␈α1-x␈α␈↓αelse␈↓↓␈α0)␈α+␈α(␈↓αif␈↓↓␈α1+x␈α<
␈↓ ↓H␈↓↓-1 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ 1+x < 0 ␈↓αthen␈↓↓ 1+1+x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ 1+x < 1 ␈↓αthen␈↓↓ 1-(1+x) ␈↓αelse␈↓↓ 0)

␈↓ ↓H␈↓↓                =␈α
(␈↓αif␈↓↓␈α
x␈α<␈α
-2␈α
␈↓αthen␈↓↓␈α
0␈α␈↓αelse␈↓↓␈α
␈↓αif␈↓↓␈α
x␈α
<␈α-1␈α
␈↓αthen␈↓↓␈α
0␈α
␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈α
x␈α
<␈α
0␈α␈↓αthen␈↓↓␈α
1+x␈α
␈↓αelse␈↓↓␈α
␈↓αif␈↓↓␈αx␈α
<␈α
1␈α␈↓αthen␈↓↓␈α
1-x
␈↓ ↓H␈↓↓␈↓αelse␈↓↓␈α0)␈α+␈α(␈↓αif␈↓↓␈αx␈α<␈α-2␈α␈↓αthen␈↓↓␈α0␈α␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈αx␈α<␈α-1␈α␈↓αthen␈↓↓␈α2+x␈α␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈αx␈α<␈α0␈α␈↓αthen␈↓↓␈α-x␈α␈↓αelse␈↓↓␈α␈↓αif␈↓↓␈αx␈α<␈α1␈α␈↓αthen␈↓↓␈α0␈α␈↓αelse␈↓↓
␈↓ ↓H␈↓↓0)

␈↓ ↓H␈↓↓␈↓ α_= ␈↓αif␈↓↓ x < -2 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x < -1 ␈↓αthen␈↓↓ 2+x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x < 0 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x < 1 ␈↓αthen␈↓↓ 1-x ␈↓αelse␈↓↓ 0␈↓.

␈↓ ↓H␈↓↓␈↓αRecursion␈↓

␈↓ ↓H␈↓␈↓ α_A␈α⊂common␈α⊃use␈α⊂of␈α⊃conditional␈α⊂expressions␈α⊂in␈α⊃computer␈α⊂science␈α⊃is␈α⊂for␈α⊃defining␈α⊂functions
␈↓ ↓H␈↓recursively.  Thus we can define the factorial function by

␈↓ ↓H␈↓8)␈↓ α8  ␈↓↓n! ← ␈↓αif␈↓↓ n = 0 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ n␈↓π * ␈↓↓(n - 1)!␈↓,

␈↓ ↓H␈↓where␈α∞the␈α∞symbol␈α∞←␈α∞means␈α∞that␈α∞␈↓↓n!␈↓␈α∞is␈α∞to␈α∞be␈α∞evaluated␈α∞by␈α∞evaluating␈α∞the␈α∞right␈α∞hand␈α∞side␈α∂of␈α∞(8),
␈↓ ↓H␈↓using␈α∩(8)␈α∩whenever␈α∩it␈α∩is␈α⊃necessary␈α∩to␈α∩evaluate␈α∩a␈α∩factorial.␈α⊃ In␈α∩order␈α∩to␈α∩make␈α∩such␈α⊃recursive
␈↓ ↓H␈↓definitions␈αwork,␈α
we␈αmust␈α
adhere␈αto␈α
the␈αrule␈α
that␈αif␈α
␈↓↓p␈↓␈αis␈α
true␈αwe␈α
take␈α␈↓↓a␈↓␈α
without␈αevaluating␈α␈↓↓b␈↓␈α
while
␈↓ ↓H␈↓if␈α
␈↓↓p␈↓␈α
is␈α
false␈αwe␈α
evaluate␈α
␈↓↓b␈↓␈α
without␈αevaluating␈α
␈↓↓a.␈↓␈α
 Otherwise,␈α
using␈α(8)␈α
to␈α
evaluate␈α
0!␈αwould␈α
involve
␈↓ ↓H␈↓the␈α∪computation␈α∀of␈α∪(-1)!␈α∀which␈α∪would,␈α∀following␈α∪the␈α∀definition,␈α∪run␈α∀on␈α∪forever.␈α∀ Thus␈α∪the
␈↓ ↓H␈↓evaluation of 2! then takes the form
␈↓ ↓H␈↓9)␈↓ α8  ␈↓↓2!    = ␈↓αif␈↓↓ (2 = 0) ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ 2␈↓π * ␈↓↓(2 - 1)!
␈↓ ↓H␈↓↓                = 2␈↓π * ␈↓↓1!
␈↓ ↓H␈↓↓                = 2␈↓π * ␈↓↓(␈↓αif␈↓↓ 1 = 0 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ 1␈↓π * ␈↓↓(1 - 1)!)
␈↓ ↓H␈↓↓                = 2␈↓π * ␈↓↓1␈↓π * ␈↓↓0!
␈↓ ↓H␈↓↓                = 2␈↓π * ␈↓↓1␈↓π * ␈↓↓(␈↓αif␈↓↓ 0 = 0 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ 0␈↓π * ␈↓↓(0 - 1)!)
␈↓ ↓H␈↓↓                = 2␈↓.

␈↓ ↓H␈↓␈↓ α_If␈αwe␈αstart␈α
from␈αthe␈αsuccessor␈αfunction␈α
␈↓↓n' = n + 1␈↓␈αthe␈αconstant␈α
0,␈αand␈αthe␈αequality␈α
predicate,
␈↓ ↓H␈↓we␈α⊂can␈α⊂get␈α⊂all␈α⊃partial␈α⊂functions␈α⊂on␈α⊂the␈α⊂non-negative␈α⊃integers␈α⊂that␈α⊂are␈α⊂computable␈α⊃by␈α⊂Turing
␈↓ ↓H␈↓machines␈α
by␈α∞repeated␈α
use␈α
of␈α∞recursive␈α
conditional␈α
expressions.␈α∞ Programs␈α
in␈α
the␈α∞LISP␈α
language
␈↓ ↓H␈↓for␈α∞computing␈α∞with␈α∞symbolic␈α∞expressions␈α∞are␈α∞defined␈α∞by␈α∞such␈α∞conditional␈α∂expression␈α∞recursions.
␈↓ ↓H␈↓(McCarthy 1963) and (McCarthy 1960) describe these matters.

␈↓ ↓H␈↓␈↓ α_The reader may try his hand at the recursive definition

␈↓ ↓H␈↓10)␈↓ α8  ␈↓↓f(x) ← ␈↓αif␈↓↓ x > 100 ␈↓αthen␈↓↓ x - 10 ␈↓αelse␈↓↓ f(f(x + 11))␈↓

␈↓ ↓H␈↓and show that the function it defines may also be written

␈↓ ↓H␈↓11)␈↓ α8 ␈↓↓f(x) ← ␈↓αif␈↓↓ x > 100 ␈↓αthen␈↓↓ x - 10 ␈↓αelse␈↓↓ 91␈↓.
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓The function defined by

␈↓ ↓H␈↓12)␈↓ α8 ␈↓↓f(x) ← ␈↓αif␈↓↓ x = 1 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ 2|x ␈↓αthen␈↓↓ f(x/2) ␈↓αelse␈↓↓ f(3x + 1)␈↓

␈↓ ↓H␈↓seems to always evaluate to 1, but no-one has been able to prove it.


␈↓ ↓H␈↓αTheory of conditional expressions.

␈↓ ↓H␈↓␈↓ α_The␈α∂theory␈α∞of␈α∂conditional␈α∞expressions␈α∂is␈α∞a␈α∂generalization␈α∞of␈α∂propositional␈α∞calculus␈α∂in␈α∞the
␈↓ ↓H␈↓following␈αrespect.␈α Propositional␈αfunctions␈αtake␈αthe␈αtruth␈αvalues␈α␈↓↓T␈↓␈αand␈α␈↓↓F␈↓␈αas␈αarguments␈αand␈αhave
␈↓ ↓H␈↓truth␈α∂values␈α∂as␈α∂values.␈α∂ Conditional␈α∂expressions␈α⊂take␈α∂truth␈α∂values␈α∂as␈α∂arguments␈α∂but␈α⊂take␈α∂their
␈↓ ↓H␈↓values in an arbitrary domain, e.g. the integers, real numbers or symbolic expressions.

␈↓ ↓H␈↓␈↓ α_In the first place, if ␈↓↓a␈↓ and ␈↓↓b␈↓ are truth values, then

␈↓ ↓H␈↓13)␈↓ α8 ␈↓↓␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ b ≡ (p ∧ a) ∨ (¬p ∧ b)␈↓

␈↓ ↓H␈↓so␈αthat␈αwhen␈α␈↓↓a␈↓␈αand␈α␈↓↓b␈↓␈αare␈αrestricted␈α
to␈αhave␈α␈↓↓T␈↓␈αand␈α␈↓↓F␈↓␈αas␈αvalues,␈αconditional␈αexpressions␈α
just␈αgive
␈↓ ↓H␈↓rise␈α∪to␈α∪a␈α∀ternary␈α∪propositional␈α∪connective␈α∀-␈α∪and␈α∪one␈α∀which␈α∪was␈α∪studied␈α∀before␈α∪conditional
␈↓ ↓H␈↓expressions became popular.  See (Church 1956).  Conversely,

␈↓ ↓H␈↓14)␈↓ α8 ␈↓↓p ∧ q ≡ ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ q ␈↓αelse␈↓↓ F␈↓,

␈↓ ↓H␈↓15)␈↓ α8 ␈↓↓p ∨ q ≡ ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ T ␈↓αelse␈↓↓ q␈↓,

␈↓ ↓H␈↓and

␈↓ ↓H␈↓16)␈↓ α8 ␈↓↓¬p ≡ ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ F ␈↓αelse␈↓↓ T␈↓.

␈↓ ↓H␈↓␈↓ α_We␈α∪can␈α∪form␈α∪compound␈α∪conditional␈α∪expressions␈α∪some␈α∪of␈α∪whose␈α∪terms␈α∪are␈α∩conditional
␈↓ ↓H␈↓expressions, and they satisfy identities like

␈↓ ↓H␈↓17)␈↓ α8 ␈↓↓␈↓αif␈↓↓ p ␈↓αthen␈↓↓ (␈↓αif␈↓↓ q ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ b) ␈↓αelse␈↓↓ c = ␈↓αif␈↓↓ q ␈↓αthen␈↓↓ (␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ c) ␈↓αelse␈↓↓ (␈↓αif␈↓↓ p ␈↓αthen␈↓↓ b ␈↓αelse␈↓↓ c)␈↓

␈↓ ↓H␈↓Any␈αcandidate␈αfor␈αsuch␈αan␈αidentity␈αcan␈αbe␈αchecked␈αby␈αtruth␈αtables␈αin␈αthe␈αsame␈αway␈αa␈αformula␈αof
␈↓ ↓H␈↓propositional calculus can be checked to see if it is a tautology.

␈↓ ↓H␈↓␈↓ α_There␈αare␈αalso␈αcanonical␈αforms␈αfor␈αcompound␈αconditional␈αexpressions␈αanalogous␈αto␈αthose␈αof
␈↓ ↓H␈↓propositional␈α∪calculus,␈α∪and␈α∩there␈α∪are␈α∪algorithms␈α∩for␈α∪transforming␈α∪any␈α∪compound␈α∩conditional
␈↓ ↓H␈↓expression into any of these canonical forms.  Details are given in (McCarthy 1963).

␈↓ ↓H␈↓␈↓ α_There is also a useful distributive law, namely

␈↓ ↓H␈↓18)␈↓ α8 ␈↓↓f(␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ b) = ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ f(a) ␈↓αelse␈↓↓ f(b)␈↓.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓␈↓ εH␈↓ 93


␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of CONDIT[W77,JMC] PUBbed at 12:59 on March 28, 1977.␈↓
␈↓ ↓H␈↓␈↓ εH␈↓ 94


␈↓ ↓H␈↓Possible␈α
additional␈αtopics␈α
1.␈αundefined␈α
truth␈αtable␈α
and␈αcanonical␈α
forms␈α2.␈α
the␈αgeneralized␈α
law␈αof
␈↓ ↓H␈↓substitution␈αof␈αequals␈αfor␈αequals␈α3.␈αwffs␈αand␈αterms␈α4.␈αmore␈αexamples␈αof␈αconditional␈αexpressions␈α5.
␈↓ ↓H␈↓discussion␈α
of␈α
arguments␈α
by␈α∞cases␈α
6.␈α
Use␈α
of␈α∞propositional␈α
connective␈α
for␈α
recursive␈α∞definition␈α
and
␈↓ ↓H␈↓the unsymmetrical connectives.